#define _CRT_SECURE_NO_WARNINGS 1
typedef int QueueData;

typedef struct QueueNode
{
    struct QueueNode* next;
    QueueData data;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;

typedef struct
{
    Queue q1;
    Queue q2;
}MyStack;

void QueueInit(Queue* q)
{
    assert(q);
    q->head = q->tail = NULL;
    q->size = 0;
}

QNode* BuyQNode(int x)
{
    QNode* NewNode = (QNode*)malloc(sizeof(QNode));
    if (NewNode == NULL)
    {
        perror("malloc fail");
    }

    NewNode->data = x;
    NewNode->next = NULL;

    return NewNode;
}

void QueuePush(Queue* q, int x)
{
    assert(q);

    if (q->head == NULL)
    {
        assert(!q->tail);
        QNode* Node = BuyQNode(x);
        q->head = q->tail = Node;
        q->size++;
    }
    else
    {
        QNode* Node = BuyQNode(x);
        q->tail->next = Node;
        q->tail = Node;
        q->size++;
    }
}

void QueuePop(Queue* q)
{
    assert(q);
    assert(q->size);

    if (q->size == 1)
    {
        free(q->head);
        q->head = q->tail = NULL;
    }
    else
    {
        QNode* next = q->head->next;
        free(q->head);
        q->head = next;
    }

    q->size--;
}

void QueueFree(Queue* q)
{
    assert(q);

    QNode* cur = q->head;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }

    q->head = q->tail = NULL;
    q->size = 0;

}

MyStack* myStackCreate()
{
    MyStack* Stack = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&(Stack->q1));
    QueueInit(&(Stack->q2));

    return Stack;
}

void myStackPush(MyStack* obj, int x)
{
    assert(obj);

    Queue* unemptyq = &(obj->q1);
    if (obj->q1.size == 0)
    {
        Queue* unemptyq = &(obj->q2);
    }

    QueuePush(unemptyq, x);
}

int myStackPop(MyStack* obj)
{
    assert(obj);

    if (obj->q1.size != 0)
    {
        int count = obj->q1.size - 1;
        while (count--)
        {
            QueuePush(&(obj->q2), obj->q1.head->data);
            QueuePop(&(obj->q1));
        }
        int top = obj->q1.tail->data;
        QueuePop(&(obj->q1));
        return top;
    }
    else
    {
        int count = obj->q2.size - 1;
        while (count--)
        {
            QueuePush(&(obj->q1), obj->q2.head->data);
            QueuePop(&(obj->q2));
        }
        int top = obj->q2.tail->data;
        QueuePop(&(obj->q2));
        return top;
    }
}

int myStackTop(MyStack* obj)
{
    assert(obj);

    if (obj->q1.size != 0)
    {
        return obj->q1.tail->data;
    }
    else
    {
        return obj->q2.tail->data;
    }

}

bool myStackEmpty(MyStack* obj)
{
    if ((obj->q1.size == 0) && (obj->q2.size == 0))
        return true;
    else
        return false;
}

void myStackFree(MyStack* obj)
{
    assert(obj);

    QueueFree(&(obj->q1));
    QueueFree(&(obj->q2));

    free(obj);
}